Phạm Mại là người hương Kính Chủ, huyện Giáp Sơn, phủ Tân Hưng; nay là xã Hoành Sơn, thị xã Kinh Môn, tỉnh Hải Dương.

Ông nguyên họ Chúc, tên Cố; sau Trần Nhân Tông (ở ngôi: 1285-1293) cho rằng họ Chúc không phải là họ lớn, mới cho đổi thành họ Phạm, còn tên Cố vì trùng với tên thầy học Nguyễn Sĩ Cố nên đổi thành Mại[1].

Theo tài liệu thì ba cha con ông đều hay thơ. Cha (không rõ tên) là nhà sư ở Phù Thạch (Hà Tĩnh), em là Phạm Ngộ (hay Phạm Tông Ngộ), làm quan đồng thời với ông [2].

Không rõ Phạm Mại có thi đỗ gì không, chỉ biết khi Trần Nhân Tông xuất gia (Kỷ Hợi, 1299), Phạm Mại và Phạm Ngộ đều được cử làm Thị nội học sinh để theo hầu [1].

Đầu đời Trần Minh Tông (ở ngôi: 1314-1323), Phạm Mại được cử đi sứ sang Nguyên (Trung Quốc) cùng với Nguyễn Trung Ngạn. Khi về nước, ông được làm chức Ngự sử trung tán, rồi lần lượt thăng đến chức Môn hạ sảnh đồng tri [3].

Theo sách Nam Ông mộng lục của Hồ Nguyên Trừng, khi Phạm Mại đang giữ chức Ngự sử trung thừa, thì bị cách chức trong vụ án Trần Quốc Chẩn [4]. Sau khi Quốc Chẩn được minh oan, Phạm Mại mới được thăng làm Tham tri chính sự [5].

Khi ở Ngự sử đài, Phạm Mại nổi tiếng là người "cương trực dám nói, có phong cách của người bề tôi can ngăn ngày xưa" [6].